package Top101K;
/**
 * @Author quan
 * @Description 反转链表：有很多种解法，还可以使用堆栈等，递归的方式也有很多写法，后续研究 1
 * @Date 2023/12/5 10:50
 */
public class BM1_ReverseList {
    /**
     * 方法1：头插法+双指针+在原链表上完成
     * @param head {5,4,3,2,1}
     * @return {1,2,3,4,5}
     */
//    public ListNode ReverseList (ListNode head) {
//        // write code here
//        // 1-边界情况
//        if(head == null){
//            return null;
//        }
//        //2-定义两个指针
//        ListNode pre = null;
//        ListNode cur = head;
//        //3-在原链表上移动
//        while (cur != null){
//            // 保存cur的下一个节点
//            ListNode temp = cur.next;
//            // 更改cur的指向
//            cur.next = pre;
//            // 更新pre和cur的位置，右移一位
//            pre = cur;
//            cur = temp;
//        }
//        // 4-最后pre所指的节点就是反转后链表的头结点
//        return pre;
//    }

    /**
     * 方法2：虚拟头结点+头插法+不在原链表上移动
     * 定义一个虚拟头结点，每次遍历到链表中的一个节点，就产生一个与该节点值相同的新节点，头插到虚拟头结点之后，最后要返回的头结点就是dummyHead
     * @param head 头结点
     * @return 反转后链表的头结点
     */
//    public ListNode ReverseList (ListNode head) {
//        // 边界条件
//        if(head == null || head.next == null){
//            return head;
//        }
//        // 1-创建虚拟头结点
//        ListNode dummyHead = null;
////        dummyHead.next = head;
//        // 2-遍历链表
//        ListNode cur = head;
//        while (cur != null){
//            ListNode newNode = new ListNode(cur.val);
//            // 将新节点头插到虚拟头结点处
//            newNode.next = dummyHead;
//            // 更新虚拟头结点的位置
//            dummyHead = newNode;
//            cur = cur.next;
//        }
//        return dummyHead;
//    }
    /**
     * 方法3：递归法：保留原有头结点，fan拽剩余的子链表，连接头结点与返回咋后链表的尾部
     * @param head 链表头结点
     * @return 反转链表的头结点
     */
//    public ListNode ReverseList (ListNode head) {
//        // 1-边界条件
//        if(head == null || head.next == null){
//            return head;
//        }
//        // 2-找到要反转的子链表的头结点pre
//        ListNode pre = head.next;
//        // 3-反转子链表
//        ListNode newHead = ReverseList(pre);
//        // 4-将反转后的头结点的尾部cur
//        ListNode cur = newHead;
//        while (cur.next != null){
//            cur = cur.next;
//        }
//        // 5-断开原头结点之后的链表，与反转后的链表的尾部cur连接
//        head.next = null;
//        cur.next = head;
//        // 6-返回新的头结点
//        return newHead;
//    }

}

